﻿#pragma once
////只有key的模型
//template<class K>
//struct BTreeNode 
//{
//	BTreeNode(const K& key = K()):_left(nullptr),_right(nullptr),_key(key)
//	{	}
//	BTreeNode<K>* _left;
//	BTreeNode<K>* _right;
//	K _key;
//};
//
//template<class K>
//class BSTree
//{
//	typedef BTreeNode<K> Node;
//public:
//	BSTree():_root(nullptr)
//	{ }
//	//void _deleteBSTree(Node* root)
//	//{
//	//	if (_root == nullptr)
//	//	{
//	//		return;
//	//	}
//	//	_deleteBSTree(_root->_left);
//	//	_deleteBSTree(_root->_right);
//	//	delete _root;
//	//}
//	//~BSTree()
//	//{
//	//	_deleteBSTree(_root);
//	//}
//	bool Insert(const K& key)
//	{
//		if (_root == nullptr)
//		{
//			_root = new Node(key);
//			return true;
//		}
//		Node* cur = _root;
//		Node* prev = nullptr;
//		int flag = 1;
//		while (cur)
//		{
//			prev = cur;
//			if (cur->_key < key)
//			{
//				cur = cur->_right;
//				flag = 1;
//			}
//			else if (cur->_key > key)
//			{
//				cur = cur->_left;
//				flag = 0;
//			}
//			else
//			{
//				return false;
//			}
//		}
//		cur = new Node(key);
//		if (flag)
//		{
//			prev->_right = cur; 
//		}
//		else
//		{
//			prev->_left = cur;
//		}
//		return true;
//	}
//
//	void _InOrder(Node* root)
//	{
//		if (root == nullptr)return;
//		_InOrder(root->_left);
//		cout << root->_key << " ";
//		_InOrder(root->_right);
//	}
//	void InOrder()
//	{
//		_InOrder(_root);
//		cout << endl;
//	}
//	 Node* Find(const K& key)const
//	{
//		Node* cur = _root;
//		while (cur)
//		{
//			if (cur->_key < key)
//				cur = cur->_right;
//			else if (cur->_key > key)
//				cur = cur->_left;
//			else
//				return cur;
//		}
//		return nullptr;
//	}
//	 bool Erase(const K& key)
//	 {
//		 //首先判断是否为空，为空返回假
//		 if (_root == nullptr)return false;
//		 //再去查找要删除元素
//		 Node* cur = _root;
//		 Node* prev = nullptr;
//		 while (cur)
//		 {
//			 if (cur->_key < key)
//			 {;
//				prev = cur;
//				 cur = cur->_right;
//			 }
//			 else if (cur->_key > key)
//			 {
//				 prev = cur;
//				 cur = cur->_left;
//			 }
//			 else
//			 {
//				 break;
//			 }
//		 }
//		 //没找到则cur==nullptr返回false
//		 if (cur == nullptr)return false;
//		 ////3种情况
//		 // 1.当前节点为叶子节点//内部2种情况// 1.删除节点为根节点// 2.删除节点不为根节点
//		 if (cur->_left == nullptr && cur->_right == nullptr)
//		 {
//			 if (prev == nullptr)_root = nullptr;
//			 else {
//				 if (prev->_left == cur)prev->_left = nullptr;
//				 else prev->_right = nullptr;
//			 }
//			 delete cur;
//		 }
//		 // 2.当前节点只有一个子节点//内部2种情况// 1.删除节点为根节点// 2.删除节点不为根节点
//		 else if (cur->_left == nullptr || cur->_right == nullptr)
//		 {
//			 Node* child = cur->_left != nullptr ? cur->_left : cur->_right;
//			 if (prev == nullptr)
//			 {
//				 _root = child;
//			 }
//			 else
//			 {
//				 if (prev->_left == cur)prev->_left = child;
//				 else prev->_right = child;
//			 }
//			 delete cur;
//		 }
//		 // 3.当前节点右两个子节点
//		 else
//		 {	
//			  //找到要删除节点右子树的最小值作为被交换点
//			 Node* rMin = cur->_right;//最小值节点起始点为当前位置右子树的根
//			 Node* rMinPrev = cur;//最小值节点的父节点就应为当前位置
//			 //直到最小节点的左节点为空则找到
//			 while(rMin->_left)
//			{
//		 	 rMinPrev = rMin;
//		 	 rMin=rMin->_left;//一直向左找
//			}
//			cur->_key = rMin->_key;//被删除位置值替换为右子树最小值
//			 if (rMin == rMinPrev->_left) rMinPrev->_left = rMin->_right;
//		     else rMinPrev->_right = rMin->_right;
//			//删除被替换过的右子树最小节点
//			delete rMin;
//		 }
//		 return true;
//	 }
//private:
//	Node* _root=nullptr;
//};
//void TestBSTree1()
//{
//	cout << "TestBSTree1" << endl;
//	BSTree<int> bst1;
//	int a[] = { 5,3,4,1,7,8,2,6,0,9 };
//	for (auto e : a)
//	{
//		bst1.Insert(e);
//	}
//	bst1.InOrder();
//	int a2[] = { 5,3,4,1,7,11,8,2,6,0,9 };
//	BTreeNode<int>* ret = bst1.Find(5);
//	cout << ret->_key << endl;
//	for (auto e : a2)
//	{
//		bst1.Erase(e);
//		bst1.InOrder();
//	}
//
//	cout << "TestBSTree1" << endl;
//}



//key/value模型
template<class K,class V>
struct BTreeNode
{
	BTreeNode(const K& key = K(),const V& value=V()) :_left(nullptr), _right(nullptr), _key(key),_value(value)
	{
	}
	BTreeNode<K,V>* _left;
	BTreeNode<K,V>* _right;
	K _key;
	V _value;
};
template<class K, class V>
class BSTree
{
	typedef BTreeNode<K,V> Node;
public:
	BSTree() :_root(nullptr)
	{
	}
	
	bool Insert(const K& key, const V& value=V())
	{
		if (_root == nullptr)
		{
			_root = new Node(key,value);
			return true;
		}
		Node* cur = _root;
		Node* prev = nullptr;
		while (cur)
		{
			
			if (cur->_key < key)
			{
				prev = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				prev = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key,value);
		if (key>prev->_key)
		{
			prev->_right = cur;
		}
		else
		{
			prev->_left = cur;
		}
		return true;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)return;
		_InOrder(root->_left);
		cout << root->_key <<":"<<root->_value << " ";
		_InOrder(root->_right);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	Node* Find(const K& key)const
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
				cur = cur->_right;
			else if (cur->_key > key)
				cur = cur->_left;
			else
				return cur;
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		//首先判断是否为空，为空返回假
		if (_root == nullptr)return false;
		//再去查找要删除元素
		Node* cur = _root;
		Node* prev = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				;
				prev = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				prev = cur;
				cur = cur->_left;
			}
			else
			{
				break;
			}
		}
		//没找到则cur==nullptr返回false
		if (cur == nullptr)return false;
		////3种情况
		// 1.当前节点为叶子节点//内部2种情况// 1.删除节点为根节点// 2.删除节点不为根节点
		if (cur->_left == nullptr && cur->_right == nullptr)
		{
			if (prev == nullptr)_root = nullptr;
			else {
				if (prev->_left == cur)prev->_left = nullptr;
				else prev->_right = nullptr;
			}
			delete cur;
		}
		// 2.当前节点只有一个子节点//内部2种情况// 1.删除节点为根节点// 2.删除节点不为根节点
		else if (cur->_left == nullptr || cur->_right == nullptr)
		{
			Node* child = cur->_left != nullptr ? cur->_left : cur->_right;
			if (prev == nullptr)
			{
				_root = child;
			}
			else
			{
				if (prev->_left == cur)prev->_left = child;
				else prev->_right = child;
			}
			delete cur;
		}
		// 3.当前节点右两个子节点
		else
		{
			//找到要删除节点右子树的最小值作为被交换点
			Node* rMin = cur->_right;//最小值节点起始点为当前位置右子树的根
			Node* rMinPrev = cur;//最小值节点的父节点就应为当前位置
			//直到最小节点的左节点为空则找到
			while (rMin->_left)
			{
				rMinPrev = rMin;
				rMin = rMin->_left;//一直向左找
			}
			cur->_key = rMin->_key;//被删除位置值替换为右子树最小值
			if (rMin == rMinPrev->_left) rMinPrev->_left = rMin->_right;
			else rMinPrev->_right = rMin->_right;
			//删除被替换过的右子树最小节点
			delete rMin;
		}
		return true;
	}
private:
	Node* _root = nullptr;
};

void TestBSTree2()
{
	cout << "TestBSTree2" << endl;
	BSTree<string,string> bst1;
	bst1.Insert("sort", "排序");
	bst1.Insert("string", "字符串");
	bst1.Insert("tree", "树");
	bst1.Insert("insert", "插入");
	
	string str;
	while (cin >> str)
	{
		BTreeNode<string, string>* ret = bst1.Find(str);
		if (ret)
		{
			cout << ret->_value << endl;
		}
		else
		{
			cout << "find null" << endl;
		}
	}
	bst1.InOrder();
	cout << "TestBSTree2" << endl;
}